Image processing systems utilize image pyramids to facilitate efficient and rapid image processing. Image pyramid creation and utilization is well known in the art. For example, U.S. Pat. No. 5,325,449, issued Jun. 28, 1994 and incorporated herein by reference discloses well-known methods of generation and utilization of Laplacian image pyramids. Generally speaking, a pyramid is constructed by successive filtering and subsampling of an image to create another image, i.e., the next level in the pyramid. The successive filtering and subsampling processes are accomplished on each level of the pyramid to create the next sub layer or level. The process for constructing an image pyramid by successive filtering and subsampling is known as image reduction. To insure that all of the image information in one level (parent) is carried to the next layer (child), the filter must extend beyond the image boundaries to ensure that the center of the filter is aligned with the edge most pixel. This ensures that the information within the edge most pixel of the image is filtered and carried into the next level of the pyramid. However, to extend beyond the image boundary without truncation, the image must be circumscribed with a border area. The region of overlap into the border by the filter is known as the filter extent.
Since the border does not exist in the original image, the image must be extended to support the filter extent. The border may be created using a number of different techniques to produce pixels about the edge of the image such as image spreading, image mirroring, or by merely inserting pixels having a constant value. The typical process for generating a pyramid is to fill the border area using one of these methods, apply the filter and subsampling processes, and then repeat the process recursively on the new images in each level of the pyramid until the designated number of levels have been generated. Consequently, a border must be generated around each level of the pyramid to enable the next level to be created.
More specifically, if the filter is, for example, a five-tap filter, the filter has an extent of two. As such, the border must have two pixels extending form the edge pixels in the actual image. Without such an extent, artifacts are generated at the border areas of the image pyramid due to truncation of the filter extent. These artifacts are carried into any image that is subsequently generated by expanding the pyramid into a final image.
In general, the a Laplacian pyramid is generated by building the pyramid using a Gaussian filter having a number of taps, e.g., five. The pyramid can be expanded by expanding a lower level in the pyramid (a child level) and subsequently subtracting the expanded child level image from the parent image (the level above the child). The expansion is accomplished by first filling the border on the child's level, upsampling the pixels of the child level and then filtering the image to create an image the same size as the parent so that the level combining operation e.g., subtraction, can be performed. The process is repeated recursively until the designated levels have been processed to form a final image.
More specifically, assuming a subsample ratio 2 to 1, a pixel in the child image covers four pixels of the parent, i.e., two horizontal by two vertical pixels. For a four pyramid level pyramid, each pixel in the last child image covers 64 pixels, an 8 by 8 pixel area, of the parent image. This means that an error in the value of the pixel at the first border beyond the image in the lowest child level could significantly affect quite a few pixels inside the real image during the expansion process. Typical practice is to make the border large enough to minimize this effect. For example, if a five tap filter for the reduction and expansion process is used, the two pixel filter extent will require a six pixel border by the parent level in order to support the expansion process. A border size is generally defined by the following equation: EQU Parent Border=((2.times.Child Border)+filter extent)
As such, starting with a five tap filter having a two pixel extent and a two pixel border for the child the progression of border size is as follows:
Image 1: 2 Pixel Border PA1 Image 2: 6 Pixel Border PA1 Image 3: 14 Pixel Border PA1 Image 4: 30 Pixel Border, and so on.
As can be seen by the foregoing chart the required number of pixels grows dramatically as more levels are used. Consequently, a substantial amount of memory is required to store border pixel values. As such, to ensure that the border pixels are sufficiently accurate to create clear imagery in the final image a substantial amount of border processing is required that increases the overhead of the image processing system. Such overhead requires additional memory which increases the cost of the image processing system.
Therefore, a need exists in the art for a method and apparatus for processing border information that does not require excessive overhead or a substantial amount of memory.